﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplicationTest
{
    class Program
    {
        public static List<Item> create()
        {
            var list = new List<Item>();
            list.Add(new Item(0, 0));//0
            list.Add(new Item(1, 0));//1
            list.Add(new Item(1, 0));//2
            list.Add(new Item(2, 0));//3
            list.Add(new Item(2, 0));//4
            list.Add(new Item(2, 0));//5
            list.Add(new Item(1, 0));//6
            list.Add(new Item(2, 0));//7
            list.Add(new Item(2, 0));//8
            list.Add(new Item(1, 0));//9
            list.Add(new Item(2, 0));//10
            list.Add(new Item(3, 0));//11
            list.Add(new Item(3, 0));//12
            list.Add(new Item(3, 0));//13
            list.Add(new Item(2, 0));//14
            list.Add(new Item(3, 0));//15
            list.Add(new Item(3, 0));//16
            list.Add(new Item(1, 0));//17
            return list;
        }
        public static Item process(List<Item> list)
        {
            int k = 0;
            Item citem, sitem, pitem, cparent, ritem;
            Stack<Item> s = new Stack<Item>();
            s.Push(list[0]);
            pitem = list[0];
            ritem = list[0];
            for (int i = 1; i < list.Count; i++)
            {
                citem = list[i];
                if (citem.info > pitem.info)
                {
                    citem.parent = (i-1);
                    s.Push(citem);
                    cparent = list[i - 1];
                }
                else if (citem.info == pitem.info)
                {
                    citem.parent = pitem.parent;
                    cparent = pitem;
                }
                else
                {
                    k = pitem.info;
                    while (citem.info < k)
                    {
                        s.Pop();
                        k--;
                    }
                    if(s.Count==0) s.Push(list[0]);
                    sitem=s.Peek();
                    citem.parent = sitem.parent;
                    cparent = sitem;
                }
                pitem = citem;
                if (ritem.info == cparent.parent)
                {
                    if (ritem.items.Contains(cparent) == false)
                        ritem.items.Add(cparent);
                }
            }
            for (int i = 1; i < list.Count; i++)
            {
                if(list[i].items.Count>0)
                    Console.WriteLine(i + ":" + list[i].info + "-" + list[i].parent);
            }
            return ritem;
        }
        static void Main(string[] args)
        {
            Program.process(Program.create());
            Console.Read();
        }
    }
    public class Item
    {
        public int info;
        public int parent;
        public List<Item> items;
        public Item(int a, int b)
        {
            info = a;
            parent = b;
            items = new List<Item>();
        }
    }
}
